#include <vector>
#include <string>

using namespace std;

// 309. 买卖股票的最佳时机含冷冻期
class Solution 
{
public:
    int maxProfit(vector<int>& prices) 
    {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(3));
        dp[0][0] = -prices[0];
        for(int i = 1; i < n; ++i)
        {
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
            dp[i][2] = dp[i - 1][0] + prices[i];
        }
        return max(dp[n - 1][1], dp[n - 1][2]);
    }
};

// 5. 最长回文子串
class Solution 
{
public:
    string longestPalindrome(string s) 
    {
        int begin = 0, len = 0, n = s.size();
        for(int i = 0; i < n; ++i)
        {
            int left = i, right = i;
            while(left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
            }
            if(right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }

            left = i, right = i + 1;
            while(left >= 0 && right < n && s[left] == s[right])
            {
                --left;
                ++right;
            }
            if(right - left - 1 > len)
            {
                begin = left + 1;
                len = right - left - 1;
            }
        }

        return s.substr(begin, len);
    }
};

// 186. 反转字符串中的单词 II
class Solution 
{
public:
    void reverseWords(vector<char>& s) 
    {
        reverse(s.begin(), s.end());
        int pos = 0, prev = 0, n = s.size();
        while(pos < n)
        {
            if(s[pos] == ' ')
            {
                reverse(s.begin() + prev, s.begin() + pos);
                prev = pos + 1;
            }
            ++pos;
        }
        reverse(s.begin() + prev, s.begin() + pos);
    }
};

// 328. 奇偶链表
class Solution 
{
public:
    ListNode* oddEvenList(ListNode* head) 
    {
        if(head == nullptr) return head;
        ListNode *odd = head, *even = head->next, *evenHead = even;
        while(even && even->next)
        {
            // 将奇数节点连接起来
            odd->next = even->next;
            odd = odd->next;
            // 将偶数节点连接起来
            even->next = odd->next;
            even = even->next;
        }
        odd->next = evenHead;
        return head;
    }
};

// 205. 同构字符串
class Solution 
{
public:
    bool isIsomorphic(string s, string t) 
    {
        unordered_map<char, char> m1, m2;
        int n = s.size();
        for(int i = 0; i < n; ++i)
        {
            if(m1.count(s[i]) && m1[s[i]] != t[i]) return false;
            if(m2.count(t[i]) && m2[t[i]] != s[i]) return false;
            m1[s[i]] = t[i];
            m2[t[i]] = s[i];
        }
        return true;
    }
};